package 数据结构系列;


public class 回文链表_234 {
    class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    ListNode left;


    public boolean isPalindrome(ListNode head) {
        ListNode slow;
        ListNode fast;
        fast = slow = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        if (fast != null) {//快指针已经停止了，但是没到null，证明链表为奇数
            slow = slow.next;//因为要从slow开始反转，所以slow还要向前走一步
        }

        //left、right指针用来比较反转后二者是否相同
        ListNode left = head;
        ListNode right = reverse(slow);//right从反转后的头节点开始

        while (right != null) {
            if (left.val != right.val) {
                return false;
            }
            left = left.next;
            right = right.next;
        }

        return true;


    }

    /* 反转以head为头的链表，返回反转后的头节点*/
    ListNode reverse(ListNode head) {
        /*
        比如 1->2->3->4->3->2->1从右边的3反转后应该为
        1->2->3->4  1->2->3->null
         */
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre=cur;
            cur = next;
        }

        return pre;
    }

//   public boolean isPalindrome(ListNode head) {
//        left = head;
//        return traverse(head);
//    }
//
//    /**
//     * 利用递归，倒序遍历单链表
//     * @param right
//     * @return
//     */
//    public boolean traverse(ListNode right) {
//        if (right == null) {
//            return true;
//        }
//        boolean res = traverse(right.next);
//        //后序遍历写在这
//        res = res && (right.val == left.val);
//        left = left.next;
//        return res;
//    }
}
